package leetcode.editor.cn.dsa10_recursion;
//在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只
//能放在更大的盘子上面)。移动圆盘时受到以下限制: 
//(1) 每次只能移动一个盘子; 
//(2) 盘子只能从柱子顶端滑出移到下一根柱子; 
//(3) 盘子只能叠在比它大的盘子上。 
//
// 请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。 
//
// 你需要原地修改栈。 
//
// 示例1: 
//  输入：A = [2, 1, 0], B = [], C = []
// 输出：C = [2, 1, 0]
//
// 示例2: 
//  输入：A = [1, 0], B = [], C = []
// 输出：C = [1, 0]
//
// 提示: 
// A中盘子的数目不大于14个。
// 
// Related Topics 递归 


import java.util.ArrayList;
import java.util.List;

public class HanotaLcc0806 {
    public static void main(String[] args) {
        Solution solution = new HanotaLcc0806().new Solution();
        List<Integer> a = new ArrayList<>();
        a.add(2); a.add(1); a.add(0);
        List<Integer> c = new ArrayList<>();
        solution.hanota(a, new ArrayList<>(), c);
        System.out.println(c); // [2, 1, 0]
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
            int size = A.size();
            // 0.准备：根据圆盘的数量确定柱子的排放顺序（使用数组存放）：
            List<Integer>[] lists = new List[3];
            lists[0] = A;
            if (size % 2 == 0) {
                // 0.1若n为奇数，按顺时针方向依次摆放 A C B
                lists[1] = B;
                lists[2] = C;
            } else {
                // 0.2若n为偶数，按顺时针方向依次摆放 A B C；
                lists[1] = C;
                lists[2] = B;
            }
            int currentIndex = 0; // 记录最小盘子所在的柱子下标
            // 循环进行两步操作法（边界条件，所有盘子都移动到C上）
            while (C.size() < size) {
                List<Integer> current = lists[currentIndex];
                // 编号最小盘子所在柱子的下一个柱子
                currentIndex = (currentIndex + 1) % 3;
                List<Integer> next = lists[currentIndex];
                // 编号最小盘子所在柱子的上一个柱子
                List<Integer> pre = lists[(currentIndex + 1) % 3];
                // 1.最小的圆盘 移动到下一个柱子
                next.add(current.remove(current.size() - 1));
                int preSize = pre.size();
                int curSize = current.size();
                // 2.另外两根柱子上可以移动的圆盘移动到新的柱子上，当两根柱子都非空时，移动较小的圆盘
                int plateToMove1 = preSize == 0 ? Integer.MAX_VALUE : pre.get(preSize - 1);
                int plateToMove2 = curSize == 0 ? Integer.MAX_VALUE : current.get(curSize - 1);
                // 较小的盘子移动到另外一个柱子
                if (plateToMove1 < plateToMove2) {
                    current.add(pre.remove(preSize - 1));
                } else if (plateToMove2 < plateToMove1) {
                    pre.add(current.remove(curSize - 1));
                }
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}